package 力扣._1267_统计参与通信的服务器;

public class Solution {

    int num = 0;    //当前连通分量的节点数量

    //如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。
    void dfs(int i, int j, int[][] grid, int[][] visited) {
        visited[i][j] = 1;
        num++;
        //遍历当前行
        for (int k = 0; k < grid.length; k++) {
            if (grid[k][j] == 1 && visited[k][j] == 0)
                dfs(k, j, grid, visited);
        }
        //当前列
        for (int k = 0; k < grid[0].length; k++) {
            if (grid[i][k] == 1 && visited[i][k] == 0)
                dfs(i, k, grid, visited);
        }
    }

    public int countServers(int[][] grid) {
        int[][] visited = new int[grid.length][grid[0].length];
        int sum = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j] == 0 && grid[i][j] == 1) {
                    num = 0;
                    dfs(i, j, grid, visited);
                    if (num > 1)
                        sum += num;
                }
            }
        }
        return sum;
    }
}
